1. Field of the Invention
The present invention relates to content-addressable memories (CAMs) and, in particular, to test algorithms for testing CAMs.
2. Description of the Related Art
Computer memory cells are in wide use today. Each memory cell stores a bit of data, i.e. a logic-0 or logic-1, sometimes referred to as low or high, respectively, corresponding to the low voltage state (typically VSS, e.g. ground=0V)) or the high voltage state (typically VDD, e.g. 3V). New data may be written into the cell, and stored data may be read from the cell. This is typically done by xe2x80x9cenablingxe2x80x9d the cell by providing a control signal to a control input terminal, which allows data in the cell to be read out on a second, data terminal (or data provided on the data terminal is written in the cell in a write operation).
An array of memory cells are typically provided in a memory array architecture. In a memory cell array, each row of memory cells is typically used to provide storage of larger, multi-bit units of data such as bytes or words. The memory array provides a number of rows or words to provide multiple word storage.
Memory arrays can be implemented in various forms, including Flash EEPROM, DRAM, ROM, and SRAM. Memory arrays are increasingly used in integrated circuits (ICs) in devices such as cellular telephones, answering machines, cordless phones, and other applications. Content-addressable memories (CAMs) are also used in various applications. Memory devices such as CAM, RAM, and other memory devices may be fabricated as part of an IC within a semiconductor chip. Chips are formed in the substrate of a physical wafer, e.g. a silicon wafer. Typically, several chips are formed on each wafer. A wafer is a very thin, flat disc of a given diameter. The manufacturing process consists of operations on the surface and substrate of the wafer to create a number of chips. Once the wafer is completely processed, it is cut up into the individual chips, the size of which depends on the number of components and complexity of each chip.
Each byte of memory typically is addressable by its address. Unlike RAM, however, which searches for data at a particular address. CAMS also allow bytes to be accessed by the content of the bytes themselves, not only by their address. A CAM can provide a standard memory operation, such as read/write data from/to the memory location specified by the address inputs. A CAM can also provide a search function, whereby any content stored in the CAM can by searched directly without using address input. The standard read/write operation of a CAM is typically similar to the read/write operation of an SRAM.
CAMs are used in several applications, such as look-up tables and artificial neural networks. A CAM may be used in an electronic spelling checker, for example, where a CAM-based dictionary is searched to locate a word with a specific spelling. If there is at least one word with the same spelling as the input word, the search will be successful. As the semiconductor industry""s average cost per gate continues to drop, CAMs are finding ever-wider application. Today, large CAMs (greater than 1 Kb) are also being used for memory management, database management, and data flow computing architectures.
A typical CAM includes an array of core cells and comparators, so as to perform the dual functions of storage of a bit of data and comparison of the stored bit to applied reference data. Some CAMs contain a plurality of comparators (e.g., exclusive OR (XOR) gates) in addition to the core memory cells, each comparator being associated with a separate one of the memory cells in each row of the array. The comparators associated with the memory cells in each row have their outputs logically combined with each other, providing the CAM with the advantage of matching a match word to the word stored in each row of the array. In addition, some CAMs also offer a feature known as a xe2x80x9cwild cardxe2x80x9d which allows masking of selected bits of the match word. Thus, CAMs are similar to conventional RAMs in that they contain a matrix array of memory cells which can be used to write/read data in random fashion; but they also provide the content-addressable matching features of CAMs.
In particular, a CAM is a memory array with ancillary circuitry to provide priority matching (with or without wild card capabilities) that can return the address of the first (lowest) addressed memory element that matches a given input (reference). In CAMs such as the Lucent Standard-Cell CAM in the Lucent Technologies(trademark) Standard Cell Library (see LV250C 2.5Volt: 0.25 xcexcm CMOS Standard-Cell Library, Lucent Technologies 1998), a CAM may provide, for example, 1024 entries, each of which has up to 72 bits. In general, a CAM is assumed to have E entries each of which has N bits plus an additional xe2x80x9cvalid bitxe2x80x9d. The entries are addressed with M address bits, with the addresses starting at 0 and running to a maximum of 2Mxe2x88x921 where, in matching, the numerically smaller (lower) addresses have higher priority. In addition to having priority matching, this core also allows for bit writing, wild card matching, and a valid bit associated with each entry. The valid bit is writable, and searches can be restricted to only valid entries, only invalid entries, or all entries. The valid bit may be used in this manner to avoid having to write or erase all of the cells, e.g. upon start-up, which might otherwise be required to ensure that random or meaningless data does not cause an erroneous search result.
In a CAM such as a Lucent Standard-Cell CAM, a match operation is used to realize the search function to find data. The match operation uses a Match Search input and generates a Match Address output and related Match Address output information such as a 3-state Match Address output, a Match output flag, and a Multiple Match output. In the match operation, the value of the Match Search input is compared to the data content of each entry in the CAM. If a match exists between the Match Search input and any of the memory content, the Match output flag will go high and the Match Address output will change to the lowest significant address location where a match occurred. If a match does not occur, the Match flag will go low. If more than one match exists, the Multiple Match flag will go low.
In a wild card operation, the user can ignore bits of the data in the match operation. For example, if the nth bit of the wildcard (WC) is high, the nth bit of the entries will not be compared to the corresponding bit of the match search input; the rest of the Nxe2x88x921 bits will be used for the comparison.
Memory tests of semiconductor memory devices such as RAM ICs (e.g., DRAMs and SRAMs) are typically performed by the manufacturer during production and fabrication to ensure correct functioning. Such devices are also sometimes tested by downstream manufacturers of computer systems embodying the RAMs, as well as by an end user during computer initialization, to determine if the circuits are operating as intended. The testing is typically performed by a memory controller or processor (or a designated processor in a multi-processor machine) which runs a testing program or algorithm.
RAMs are usually subjected to data march tests and data retention tests. In a march or marching test, a sequence of read and/or write operations is applied to each cell of the memory array or matrix, either in increasing or decreasing address order; i.e., patterns are marched across the memory array. A march test is analogous to a walking bit test, but done on a word basis, and is able to detect various types of faults. Various types of march tests detect different types of faults in varying amounts of time. In the March LR test, for example, the following types of faults may be detected: stuck open faults; stuck at faults; transition faults; coupling faults, including CFins (inversion coupling), CFids (Idempotent coupling), CFsts (state coupling), and CFdsts (coupled disturb); linked faults (linked faults appear as more than one fault that interact, therfore more than one type of fault can be linked); AF (address faults); TF (transition faults); address decoding faults, including no access faults, wrong access faults, multiple access faults, and address bit transition faults; column multiplexer stuck at faults; bit write faults; and I/O bus faults.
March tests are particularly popular for built-in self-test (BIST) techniques, because they can be efficiently implemented with a small amount of hardware, with predictable fault coverage, as noted above with respect to the March LR test. In general, therefore, the memory cell arrays of RAMs, such as SRAMs, are tested with memory array tests such as a march test.
In data retention tests, every cell of the memory is written and checked after a pre-specified interval to determine if leakage current has occurred that has affected the stored logic state.
Such memory array testing ensures that hidden defects will not be first discovered during operational use, thereby rendering end-products unreliable. March tests and other techniques are described in further detail in A. J. van de Goor, Testing Semiconductor Memories: Theory and Practice (New York: Wiley and Sons, 1996); and A. J. van de Goor, G. N. Gaydadjiev, V. N. Yarmolik and V. G. Mikitjuk, xe2x80x9cMarch LR: A Test for Realistic Linked Faults,xe2x80x9d 14th VLSI Test Symposium, pp. 272-280; A. J. van de Goor, et al., xe2x80x9cEffective March Algorithms for Testing Single-Order Addressed Memories,xe2x80x9d Journal of Electronics Testing: Theory and Applications,Vol.5, No.4, pp. 337-345, November 1994.
There is also a need to test CAMs. Often the CAM tests itself upon power-up, with a BIST. CAMs may also be tested externally. Providing a complex, very large scale IC (VLSIC) with BIST capability allows very high fault coverage to be obtained without the need for sophisticated external test equipment. Because of the different designs of various types of memories (RAMs, ROMs, FIFOs, etc.), separate BIST techniques are required for such different functional structures.
As noted above, CAMs are similar to conventional RAMs but also have matching and possible wild card features. The matching and wild card features of CAMs cause them to be more complex as compared to other types of memories such as RAM. For that reason, current BIST and other testing techniques used for RAMs are not always suitable for CAMs. There is, therefore, a need for CAM testing techniques (either used as a BIST or as an external test) which test the functionality of all of the features and functions of the CAMs, including matching and the wild card and valid bit functions described above.
In the present invention, a method is provided for testing the functionality of a content-addressable memory (CAM) having a memory array for storing data, the memory array having E entries each having N data bits and a valid bit. First, the memory array is tested for read/write functionality. The functionality of a matching function, a priority encoding function, a match flag function, and a multiple match flag function of the CAM is tested. The functionality of an invalidate data function and a valid data restricted search function is also tested.